Some standards for encoding and decoding videos (e.g., ITU-T H.264/AVC video coding standard) use block-based coding processes. In these processes, to compress a video sequence, which consists of several frames of pictures, a frame is divided into blocks (e.g., 4×4, 8×8, 16×16, 32×32, or 64×64 blocks of pixel data). In this way, the task of coding the whole video sequence is broken down into coding each block, where blocks within a frame are coded in a certain order (e.g., raster order). The process of coding a block includes performing a transform (e.g., the discrete cosine transform (DCT)). In many cases, the data being transformed is not the actual pixel data, but is residual data following a prediction operation. For example, to code a particular block of pixels (called the “current block”), a prediction of the same size (called the “reference block”) is derived based on reconstruction of a block that was already coded according to the coding order. The reference block can come from a different frame (called “inter prediction”) or the same frame (called “intra prediction”). A residual block is obtained by subtracting the reference block from current block. Each residual block is transformed into a block of transform coefficients, the transform coefficients are optionally quantized, and the (possibly quantized) transform coefficients are entropy encoded, yielding a bitstream. Decoding is performed using an inverse procedure including entropy decoding the bitstream, and de-quantizing and inverse transforming to recover the residual block. The reference block that was used to generate the residual block at the encoder can also be recovered at the decoder using previously decoded data. Then the current block is reconstructed by adding the residual block to the reference block.
The overall encoding/decoding procedure may result in lossy compression/decompression of the video data (e.g., if quantization is involved), however, the entropy encoding/decoding portion of the overall procedure is lossless. In the AVC standard, two entropy coding methods are employed in the block-wise prediction coding architecture described above: one is called context-adaptive binary arithmetic coding (CABAC) and the other one is called context-adaptive variable length coding (CAVLC).